

function ConnectedComponents( graph )
	
	local usedNodes = {}
	
	--Find a node that is not a in a graph yet
	for key, node in pairs( graph.nodes ) do
		
		if not table.contains( usedNodes, node ) then
			
			local subGraph = node:breadthFirstSearch()
			
			print("SubGraph")
			
			for node in pairs( subGraph ) do
				print("\t" .. tostring(node) )
				table.insert( usedNodes, node )
			end

		end
		
	end
	
end

local function iterateBipartiteOnNode( node )
	
	local level = 0
	local levelTable = {
		[node] = level
	}
	local biPirtiteGraph = {
		[1] = {},
		[2] = {}
	}
	local neighbors = {node} --Start with the nodes around this member
	
	while true do
		
		local modLevel = math.fmod( level, 2 )
		
		for _, node in ipairs( neighbors ) do
			levelTable[ node ] = level
			biPirtiteGraph[ modLevel + 1][ node ] = level
		end
		
		local nextNeighbors = {}
		
		for _, node in pairs( neighbors ) do
			
			for _, neighbor in ipairs( node.neighbors ) do
				if levelTable[ neighbor ] == nil then
					
					table.insert( nextNeighbors, neighbor )
				
				elseif modLevel == math.fmod( levelTable[ neighbor ], 2 ) then
					return false, neighbor
				end
			end
			
		end
		
		if #nextNeighbors == 0 then
			break
		end
		
		neighbors = nextNeighbors
		level = level + 1 --Increase the current layer by one
		
	end
	
	return true, biPirtiteGraph
end

function FindBipartiteGraphs( graph )

	local usedNodes = {}
	local SubBipartites = {}
	
	--Find a node that is not a in a graph yet
	for key, node in pairs( graph.nodes ) do
		
		if not table.contains( usedNodes, node ) then
			
			local success, bipartite = iterateBipartiteOnNode( node )
			
			if success == false then
				return false, bipartite
			end
			
			for _, subGraph in pairs( bipartite ) do
				for node in pairs( subGraph ) do
					table.insert( usedNodes, node )
				end
			end
			
			table.insert( SubBipartites, bipartite )

		end
		
	end
	
	return SubBipartites

end

function FindandPrintBipartiteGraphs( graph )
	
	local bipirtites, error_node = FindBipartiteGraphs( graph )
	
	if bipirtites == false then
		print("No Bipartitie found because of node: " .. tostring(error_node) )
		return
	end

	print("Bipartitie graph: ")
	for id, bipirtite in pairs( bipirtites ) do
		
		print("\tSubgraph " .. id .. ":") 
		
		for partid, part in pairs( bipirtite ) do
			
			print( "\t\tPart " ..partid .. ":")
			
			for node in pairs( part ) do
				print ("\t\t\t" .. tostring(node) )
			end
		
		end

	end

end



